package Offer.offer2016;

import domain.TreeNode;

import java.util.ArrayList;
import java.util.Stack;


//�ݹ�
public class Test25 
{

	public static void main(String[] args) 
	{
		TreeNode node1=new TreeNode(10);
		TreeNode node2=new TreeNode(5);
		TreeNode node3=new TreeNode(12);
		TreeNode node4=new TreeNode(4);
		TreeNode node5=new TreeNode(7);		
		node1.left=node2;
		node1.right=node3;
		node2.left=node4;
		node2.right=node5;
		node3.left=node3.right=null;
		node4.left=node4.right=null;
		node5.left=node5.right=null;		
		PathInTree.pathInTree(node1,22);
	}
    public static void findPath(TreeNode root,int target)
    {
    	if(root==null)
    		return;
    	ArrayList<Integer> array=new ArrayList<Integer>();
    	
    	int sum=0;
    	findPath(root,array,sum,target);
    }
    public static void findPath(TreeNode root,ArrayList<Integer> array,int sum,int target)
    {
    	array.add(root.val);
    	sum += root.val;
    	
    	if(root.left==null&&root.right==null&&sum==target)
    	{
    		
			System.out.print("�ҵ�·����");
			
    		for(int i=0;i<array.size();++i)
    		{
    			System.out.print(array.get(i));
    			System.out.print(" ");
    			
    		}
    	}
        if(root.left!=null)
        	findPath(root.left,array,sum,target);
        if(root.right!=null)
        	findPath(root.right,array,sum,target);
        sum -=root.val;
        array.remove(array.size()-1);
    }
}

class PathInTree{
	public static void pathInTree(TreeNode node,int sum){
		if(node == null ){
			return ;
		}
		int tmpSum = 0;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		pathInTree(node, tmpSum, sum, stack);
		return ;
	}
	public static void pathInTree(TreeNode node,int tmpSum,int sum,Stack<TreeNode> stack){
		tmpSum += node.val;
		stack.push(node);
		if(node.left == null && node.right == null){
			if(tmpSum == sum){
				System.out.print("�ҵ�·����");
				for (int i = 0; i < stack.size(); i++) {
					System.out.print(stack.get(i).val + " ");
				}
			}
		}else{
			if(tmpSum > sum){
				tmpSum -= node.val;
				stack.pop();
				return;
			}
			if(node.left != null){
				pathInTree(node.left,tmpSum,sum,stack);
			}
			if(node.right!= null){
				pathInTree(node.right,tmpSum,sum,stack);
			}
		}
		tmpSum -= node.val;
		stack.pop();
	} 
}